/*
 * Copyright (c) 2025 Huawei Technologies Co., Ltd.
 * openUBMC is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *         http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
 */

#ifndef MC_BUILTINS_SET_H
#define MC_BUILTINS_SET_H

#include "mcpy/builtins/cast.h"
#include "mcpy/builtins/detail/set_impl.h"
#include "mcpy/exception.h"
#include <algorithm>
#include <mc/traits.h>
#include <mc/variant/copy_context.h>
#include <type_traits>
#include <unordered_set>

namespace mcpy {

// ============================================================================
// 前向声明
// ============================================================================

template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>,
          typename Allocator = std::allocator<T>>
class set;

// ============================================================================
// 类型别名定义（统一弱类型，和 dict 一样）
// ============================================================================

/**
 * @brief variant_set 类型别名
 *
 * 统一弱类型的 set，所有元素类型为 mc::variant
 * 与 mc::dict 和 mc::variants 的命名风格保持一致
 *
 * Python 中的 set[int]、set[str]、set[Any] 在 C++ 都映射为 variant_set
 * Python 类型参数通过方法模板参数传递，实现类型安全
 *
 * 设计理念（参考 dict）：
 * - Python 侧保持强类型：set[int]、set[str] 类型明确
 * - C++ 侧统一弱类型：都映射为 variant_set
 * - 类型转换在 C++ 模板函数内部完成（如 set_pop<T>）
 * - 配置层通过模板参数 {T} 传递类型信息
 */
using variant_set = set<mc::variant>;

// ============================================================================
// set 容器定义
// ============================================================================

/**
 * @brief mcpy::set<T>
 * @tparam T 元素类型
 * @tparam Hash 哈希函数类型
 * @tparam KeyEqual 相等比较函数类型
 * @tparam Allocator 分配器类型
 */
template <typename T, typename Hash, typename KeyEqual, typename Allocator>
class set {
public:
    using impl_type      = detail::set_impl<T, Hash, KeyEqual>;
    using container_type = std::unordered_set<T, Hash, KeyEqual, Allocator>;
    using value_type     = T;
    using iterator       = typename container_type::iterator;
    using const_iterator = typename container_type::const_iterator;
    using size_type      = typename container_type::size_type;

    /**
     * @brief 默认构造函数（延迟初始化）
     */
    set() = default;

    /**
     * @brief 从初始化列表构造
     * @param init 初始化列表
     */
    set(std::initializer_list<T> init)
        : m_impl(mc::make_shared<impl_type>(init)) {
    }

    /**
     * @brief 从迭代器范围构造
     * @tparam InputIt 输入迭代器类型
     * @param first 起始迭代器
     * @param last 结束迭代器
     */
    template <typename InputIt>
    set(InputIt first, InputIt last) {
        if (first != last) {
            m_impl = mc::make_shared<impl_type>();
            for (auto it = first; it != last; ++it) {
                m_impl->insert(*it);
            }
        }
    }

    /**
     * @brief 从内部实现指针构造（仅供内部使用）
     * @param impl 内部实现指针
     */
    explicit set(mc::shared_ptr<impl_type> impl) : m_impl(std::move(impl)) {
    }

    /**
     * @brief 拷贝构造函数
     * @note 此操作会共享内部数据，不会复制数据
     */
    set(const set& other) = default;

    /**
     * @brief 移动构造函数
     */
    set(set&& other) noexcept = default;

    /**
     * @brief 赋值运算符
     * @note 此操作会共享内部数据，不会复制数据
     */
    set& operator=(const set& other) = default;

    /**
     * @brief 移动赋值运算符
     */
    set& operator=(set&& other) noexcept = default;

    /**
     * @brief 插入元素
     * @param item 要插入的元素
     */
    void insert(const T& item) {
        ensure_data();
        m_impl->insert(item);
    }

    void insert(T&& item) {
        ensure_data();
        m_impl->insert(std::move(item));
    }

    /**
     * @brief 批量插入元素
     * @tparam InputIt 输入迭代器类型
     * @param first 起始迭代器
     * @param last 结束迭代器
     */
    template <typename InputIt>
    void insert(InputIt first, InputIt last) {
        if (first != last) {
            ensure_data();
            for (auto it = first; it != last; ++it) {
                m_impl->insert(*it);
            }
        }
    }

    /**
     * @brief 删除元素
     * @param item 要删除的元素
     */
    void erase(const T& item) {
        if (m_impl) {
            m_impl->erase(item);
        }
    }

    /**
     * @brief 删除迭代器指向的元素
     * @param pos 迭代器位置
     * @return 指向删除元素之后元素的迭代器
     */
    iterator erase(iterator pos) {
        if (!m_impl) {
            return iterator();
        }
        return m_impl->erase(pos);
    }

    /**
     * @brief 检查是否包含指定元素
     * @param item 要检查的元素
     * @return 如果包含则返回 true
     */
    bool contains(const T& item) const {
        return m_impl ? m_impl->contains(item) : false;
    }

    /**
     * @brief 查找元素
     * @param item 要查找的元素
     * @return 指向元素的迭代器，如果未找到则返回 end()
     */
    iterator find(const T& item) {
        return m_impl ? m_impl->find(item) : iterator();
    }

    const_iterator find(const T& item) const {
        return m_impl ? m_impl->find(item) : const_iterator();
    }

    /**
     * @brief 获取元素数量
     * @return 元素数量
     */
    size_type size() const {
        return m_impl ? m_impl->size() : 0;
    }

    /**
     * @brief 检查 set 是否为空
     * @return 如果为空则返回 true
     */
    bool empty() const {
        return !m_impl || m_impl->empty();
    }

    /**
     * @brief 清空所有元素
     * @note 此操作会修改共享数据，影响所有共享该数据的对象
     */
    void clear() {
        if (m_impl) {
            m_impl->clear();
        }
    }

    // 迭代器

    /**
     * @brief 获取指向第一个元素的迭代器
     */
    iterator begin() {
        ensure_data();
        return m_impl->begin();
    }

    const_iterator begin() const {
        return m_impl ? m_impl->begin() : const_iterator();
    }

    /**
     * @brief 获取指向末尾的迭代器
     */
    iterator end() {
        ensure_data();
        return m_impl->end();
    }

    const_iterator end() const {
        return m_impl ? m_impl->end() : const_iterator();
    }

    /**
     * @brief 获取内部实现指针（仅供内部使用）
     * @return 内部实现指针
     */
    mc::shared_ptr<impl_type> get_impl() const {
        return m_impl;
    }

    /**
     * @brief 浅拷贝 set
     *
     * 创建一个新的 set，包含相同的元素（浅拷贝）。
     * 顶层 set 是独立的，但元素仍是引用（若元素是引用类型）。
     *
     * @return 浅拷贝后的 set
     */
    set copy() const {
        if (!m_impl) {
            return set();
        }
        auto copied_base = m_impl->copy();
        auto copied_impl = mc::static_pointer_cast<impl_type>(copied_base);
        return set(std::move(copied_impl));
    }

    /**
     * @brief 深拷贝 set
     *
     * 创建一个完全独立的 set 副本。
     * 如果元素类型本身具有引用语义（如嵌套容器），也会递归深拷贝。
     *
     * @param ctx 可选的深拷贝上下文，用于检测循环引用并记录已拷贝对象
     * @return 深拷贝后的 set
     *
     * @note 如果传入 ctx 参数，则使用该上下文进行循环引用检测
     * @note 如果不传入 ctx，则创建局部上下文（用于顶层调用）
     * @note 遇到循环引用时，返回已拷贝的对象，保持引用关系
     * @note 如果元素类型支持 deep_copy，会递归调用；否则直接拷贝元素
     */
    set deep_copy(mc::detail::copy_context* ctx = nullptr) const;

    // 运算符重载

    /**
     * @brief 比较两个 set 是否相等
     * @param other 另一个 set
     * @return 如果相等则返回 true
     */
    bool operator==(const set& other) const {
        if (m_impl == other.m_impl) {
            return true;
        }
        if (!m_impl || !other.m_impl) {
            return empty() && other.empty();
        }
        return *m_impl == *other.m_impl;
    }

    /**
     * @brief 比较两个 set 是否不相等
     * @param other 另一个 set
     * @return 如果不相等则返回 true
     */
    bool operator!=(const set& other) const {
        return !(*this == other);
    }

private:
    /**
     * @brief 共享的数据指针
     */
    mc::shared_ptr<impl_type> m_impl;

    /**
     * @brief 确保数据已初始化
     */
    void ensure_data() {
        if (!m_impl) {
            m_impl = mc::make_shared<impl_type>();
        }
    }
};

// ============================================================================
// set 辅助函数
// ============================================================================

template <typename T, typename Hash, typename KeyEqual, typename Allocator, typename U>
bool set_contains(const set<T, Hash, KeyEqual, Allocator>& s, const U& item) {
    return s.contains(item);
}

template <typename U, typename = std::enable_if_t<!std::is_same_v<U, mc::variant>>>
bool set_contains(const set<mc::variant>& s, const U& item) {
    return s.find(mc::variant{item}) != s.end();
}

// set.remove(item) - 移除元素，如果不存在则抛出异常
// 用法: set_remove(my_set, value);
template <typename T>
void set_remove(set<T>& s, const T& item) {
    auto it = s.find(item);
    if (it == s.end()) {
        MC_THROW(mcpy::key_error, "元素不存在: ${item}", ("item", item));
    }
    s.erase(it);
}

// set.remove(item) 的重载版本，支持 set<mc::variant> 接受任意类型参数
template <typename U, typename = std::enable_if_t<!std::is_same_v<U, mc::variant>>>
void set_remove(set<mc::variant>& s, const U& item) {
    set_remove(s, mc::variant{item});
}

// set.union(other) - 返回两个集合的并集
// 用法: auto result = set_union(set1, set2);
template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
set<T> set_union(const set<T, Hash, KeyEqual>& s1,
                 const set<T>&                 s2) {
    set<T> result = s1.copy();
    result.insert(s2.begin(), s2.end());
    return result;
}

// set.intersection(other) - 返回两个集合的交集
// 用法: auto result = set_intersection(set1, set2);
template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
set<T> set_intersection(const set<T, Hash, KeyEqual>& s1,
                        const set<T>&                 s2) {
    set<T> result;
    for (const auto& item : s1) {
        if (set_contains(s2, item)) {
            result.insert(item);
        }
    }
    return result;
}

// set.difference(other) - 返回在 s1 中但不在 s2 中的元素
// 用法: auto result = set_difference(set1, set2);
template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
set<T> set_difference(const set<T, Hash, KeyEqual>& s1,
                      const set<T>&                 s2) {
    set<T> result;
    for (const auto& item : s1) {
        if (!set_contains(s2, item)) {
            result.insert(item);
        }
    }
    return result;
}

// set.symmetric_difference(other) - 返回对称差集（在 s1 或 s2 中，但不同时在两者中）
// 用法: auto result = set_symmetric_difference(set1, set2);
template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
set<T> set_symmetric_difference(const set<T, Hash, KeyEqual>& s1,
                                const set<T>&                 s2) {
    set<T> result;
    // 添加在 s1 中但不在 s2 中的元素
    for (const auto& item : s1) {
        if (!set_contains(s2, item)) {
            result.insert(item);
        }
    }
    // 添加在 s2 中但不在 s1 中的元素
    for (const auto& item : s2) {
        if (!set_contains(s1, item)) {
            result.insert(item);
        }
    }
    return result;
}

// set.update(other) - 将 other 的所有元素添加到 s 中（原地修改）
// 用法: set_update(my_set, other_set);
template <typename T>
void set_update(set<T>& s, const set<T>& other) {
    s.insert(other.begin(), other.end());
}

// set.intersection_update(other) - 原地更新为交集
// 用法: set_intersection_update(my_set, other_set);
template <typename T>
void set_intersection_update(set<T>&       s,
                             const set<T>& other) {
    // 创建临时集合存储要删除的元素
    mc::array<T> to_remove;
    for (const auto& item : s) {
        if (!set_contains(other, item)) {
            to_remove.push_back(item);
        }
    }
    // 删除不在交集中的元素
    for (const auto& item : to_remove) {
        s.erase(item);
    }
}

// set.difference_update(other) - 原地更新为差集
// 用法: set_difference_update(my_set, other_set);
template <typename T>
void set_difference_update(set<T>&       s,
                           const set<T>& other) {
    for (const auto& item : other) {
        s.erase(item);
    }
}

// set.symmetric_difference_update(other) - 原地更新为对称差集
// 用法: set_symmetric_difference_update(my_set, other_set);
template <typename T>
void set_symmetric_difference_update(set<T>&       s,
                                     const set<T>& other) {
    for (const auto& item : other) {
        if (set_contains(s, item)) {
            s.erase(item); // 如果已存在，删除
        } else {
            s.insert(item); // 如果不存在，添加
        }
    }
}

// set.issubset(other) - 判断 s 是否是 other 的子集
// 用法: bool result = set_issubset(set1, set2);
template <typename T>
bool set_issubset(const set<T>& s,
                  const set<T>& other) {
    if (s.size() > other.size()) {
        return false;
    }
    for (const auto& item : s) {
        if (!set_contains(other, item)) {
            return false;
        }
    }
    return true;
}

// set.issuperset(other) - 判断 s 是否是 other 的超集
// 用法: bool result = set_issuperset(set1, set2);
template <typename T>
bool set_issuperset(const set<T>& s,
                    const set<T>& other) {
    return set_issubset(other, s);
}

// set.isdisjoint(other) - 判断两个集合是否没有交集
// 用法: bool result = set_isdisjoint(set1, set2);
template <typename T>
bool set_isdisjoint(const set<T>& s,
                    const set<T>& other) {
    for (const auto& item : s) {
        if (set_contains(other, item)) {
            return false;
        }
    }
    return true;
}

/**
 * @brief 随机移除并返回一个元素（模板化，和 dict_pop 一样）
 *
 * @tparam T Python 侧的元素类型（从 set[T] 推导）
 * @param s 集合对象（C++ 侧统一为 variant_set）
 * @return T 返回的元素（自动转换类型）
 *
 * 用法：
 *   Python: s: set[int] = {1, 2, 3}; x = s.pop()
 *   C++:    mcpy::variant_set s = {1, 2, 3}; int x = mcpy::set_pop<int>(s);
 *
 * 类型转换在函数内部完成，和 dict_pop 的设计完全一致
 */
template <typename T>
T set_pop(variant_set& s) {
    if (s.empty()) {
        MC_THROW(mcpy::key_error, "pop from an empty set");
    }
    auto        it    = s.begin();
    mc::variant value = *it;
    s.erase(it);

    // 类型转换逻辑，和 dict_pop 完全一样！
    if constexpr (std::is_same_v<T, mc::variant>) {
        return value;
    } else {
        return value.template as<T>();
    }
}

// s < other - 判断 s 是否是 other 的真子集（proper subset）
// 用法: bool result = set_is_proper_subset(set1, set2);
template <typename T>
bool set_is_proper_subset(const set<T>& s,
                          const set<T>& other) {
    return s.size() < other.size() && set_issubset(s, other);
}

// s > other - 判断 s 是否是 other 的真超集（proper superset）
// 用法: bool result = set_is_proper_superset(set1, set2);
template <typename T>
bool set_is_proper_superset(const set<T>& s,
                            const set<T>& other) {
    return set_is_proper_subset(other, s);
}

// s |= other - 原地并集，返回引用
// 用法: set_ior(my_set, other_set);
template <typename T>
set<T>& set_ior(set<T>&       s,
                const set<T>& other) {
    s.insert(other.begin(), other.end());
    return s;
}

// s &= other - 原地交集，返回引用
// 用法: set_iand(my_set, other_set);
template <typename T>
set<T>& set_iand(set<T>&       s,
                 const set<T>& other) {
    set_intersection_update(s, other);
    return s;
}

// s -= other - 原地差集，返回引用
// 用法: set_isub(my_set, other_set);
template <typename T>
set<T>& set_isub(set<T>&       s,
                 const set<T>& other) {
    set_difference_update(s, other);
    return s;
}

// s ^= other - 原地对称差集，返回引用
// 用法: set_ixor(my_set, other_set);
template <typename T>
set<T>& set_ixor(set<T>&       s,
                 const set<T>& other) {
    set_symmetric_difference_update(s, other);
    return s;
}

// ============================================================================
// 全局函数支持（min, max, any, all, sorted 等）
// ============================================================================
//
// 注意：min, max, any, all, sorted, reversed, sum 等通用全局函数已在以下头文件中实现：
// - mcpy/builtins/global_functions.h: iterable_min, iterable_max, iterable_any, iterable_all,
//                                      iterable_sorted, iterable_reversed, reduce_sum, enumerate, zip_view
//
// 这些通用函数支持所有可迭代容器，包括 mcpy::set, mc::array, mcpy::list 等
// 可以直接使用：mcpy::iterable_min(my_set), mcpy::iterable_sorted(my_set) 等

// ============================================================================
// 类型转换函数
// ============================================================================

/**
 * @brief 从可迭代容器构造 set（模板化，和 dict 一样）
 *
 * @tparam T Python 侧的元素类型（从 set[T] 推导）
 * @param container 可迭代容器
 * @return variant_set 统一返回弱类型 set
 *
 * 用法：
 *   Python: s: set[int] = set([1, 2, 3])
 *   C++:    mcpy::variant_set s = mcpy::set_construct<int>(mc::array<int>{1, 2, 3});
 *
 * 元素会自动转换为 mc::variant 存储
 */
template <typename T, typename Container>
variant_set set_construct(const Container& container) {
    variant_set result;
    for (const auto& item : container) {
        result.insert(mc::variant(item));
    }
    return result;
}

/**
 * @brief 从 variant 中提取 set（用于 Any 类型转换）
 *
 * @tparam T Python 侧的元素类型
 * @param v variant 对象
 * @return variant_set 统一返回弱类型 set
 *
 * 用法：
 *   Python: s: set[int] = some_any_value
 *   C++:    mcpy::variant_set s = mcpy::set_from_any<int>(some_any_value);
 */
template <typename T>
variant_set set_from_any(const mc::variant& v) {
    return mcpy::cast<variant_set>(v);
}

/**
 * @brief 从可迭代容器创建 set
 *
 * @param container 可迭代容器
 * @return 新的 set
 */
template <typename Container>
auto set_from_iterable(const Container& container)
    -> set<typename Container::value_type> {
    using T = typename Container::value_type;
    return set<T>(container.begin(), container.end());
}

// set::deep_copy() 成员方法的实现
template <typename T, typename Hash, typename KeyEqual, typename Allocator>
set<T, Hash, KeyEqual, Allocator> set<T, Hash, KeyEqual, Allocator>::deep_copy(mc::detail::copy_context* ctx) const {
    if (!m_impl) {
        return set();
    }
    auto copied_base = m_impl->deep_copy(ctx);
    auto copied_impl = mc::static_pointer_cast<impl_type>(copied_base);
    return set(std::move(copied_impl));
}

// ============================================================================
// 集合推导式辅助函数
// ============================================================================

/**
 * @brief 集合推导式（统一返回 variant_set，和 set_construct 一致）
 *
 * @param container 源容器
 * @param func 转换函数
 * @return variant_set 统一弱类型集合
 *
 * 设计理念（和 set_construct 完全一致）：
 * - 统一返回 variant_set，无论源容器和转换函数返回什么类型
 * - 元素自动转换为 mc::variant 存储
 * - 特殊处理 variant_reference -> variant
 */
template <typename Container, typename Func>
variant_set set_comprehension(const Container& container, Func&& func) {
    variant_set result;
    for (const auto& item : container) {
        auto transformed = func(item);
        // 所有元素统一转为 variant 存储
        result.insert(mc::variant(transformed));
    }
    return result;
}

/**
 * @brief 带条件筛选的集合推导式（统一返回 variant_set）
 *
 * @param container 源容器
 * @param transform 转换函数
 * @param filter 筛选条件
 * @return variant_set 统一弱类型集合
 *
 * 设计理念（和 set_comprehension 完全一致）：
 * - 统一返回 variant_set，无论源容器和转换函数返回什么类型
 * - 元素自动转换为 mc::variant 存储
 */
template <typename Container, typename TransformFunc, typename FilterFunc>
variant_set set_comprehension_if(const Container& container,
                                 TransformFunc&&  transform,
                                 FilterFunc&&     filter) {
    variant_set result;
    for (const auto& item : container) {
        if (filter(item)) {
            auto transformed = transform(item);
            // 所有元素统一转为 variant 存储
            result.insert(mc::variant(transformed));
        }
    }
    return result;
}

/**
 * @brief 嵌套集合推导式辅助函数
 *
 * 用于处理嵌套的集合推导式，将 lambda 结果转换为强类型集合
 *
 * @param func 返回 mc::variants 的 lambda 函数
 * @return 强类型的 mcpy::set
 */
template <typename ElementType, typename Func>
variant_set set_comp_nested(Func&& func) {
    auto        temp_result = func(); // 执行 lambda，得到 mc::variants
    variant_set result;
    for (const auto& item : temp_result) {
        result.insert(mc::variant(item));
    }
    return result;
}

// ============================================================================
// to_variant / from_variant 转换函数
// ============================================================================

/**
 * @brief 将 mcpy::set 转换为 variant
 */
template <typename T, typename Hash, typename KeyEqual, typename Allocator>
void to_variant(const mcpy::set<T, Hash, KeyEqual, Allocator>& s, mc::variant& v) {
    v = s.get_impl();
}

/**
 * @brief 从 variant 转换为 mcpy::set
 */
template <typename T, typename Hash, typename KeyEqual, typename Allocator>
void from_variant(const mc::variant& v, mcpy::set<T, Hash, KeyEqual, Allocator>& s) {
    using impl_type = detail::set_impl<T, Hash, KeyEqual>;

    // 1. 如果是 set_impl，尝试直接包装
    if (v.is_extension()) {
        auto base_ext = v.as_extension();
        if (base_ext && base_ext->get_type_name() == "set") {
            auto impl = mc::dynamic_pointer_cast<impl_type>(base_ext);
            if (impl) {
                s = mcpy::set<T, Hash, KeyEqual, Allocator>(impl);
                return;
            }

            auto new_impl = mc::make_shared<impl_type>();
            base_ext->visit([&](const mc::variant& item) {
                if constexpr (std::is_same_v<T, mc::variant>) {
                    new_impl->insert(item);
                } else {
                    new_impl->insert(item.template as<T>());
                }
            });
            s = mcpy::set<T, Hash, KeyEqual, Allocator>(std::move(new_impl));
            return;
        }
    }

    // 2. 降级处理：从 array 转换
    if (v.is_array()) {
        auto        new_impl = mc::make_shared<impl_type>();
        const auto& arr      = v.get_array();
        for (const auto& item : arr) {
            if constexpr (std::is_same_v<T, mc::variant>) {
                new_impl->insert(item);
            } else {
                new_impl->insert(item.template as<T>());
            }
        }
        s = mcpy::set<T, Hash, KeyEqual, Allocator>(new_impl);
        return;
    }

    MC_THROW(mc::bad_cast_exception,
             "类型转换异常: 期望 set 或 array, 实际 ${actual}",
             ("actual", v.get_type_name()));
}

} // namespace mcpy

#endif // MC_BUILTINS_SET_H
